<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  <title>【线段树】  L3-017 森森快递 (30分)  27分WA代码.md | 蓝湖畔淅淅沥沥的雨</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="说明 - 2022-05-05 本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。  L3-017 森森快递 (30分) 森森开了一家快递公司，叫森森快递。因为公司刚刚开张，所以业务路">
<meta property="og:type" content="article">
<meta property="og:title" content="【线段树】  L3-017 森森快递 (30分)  27分WA代码.md">
<meta property="og:url" content="http://example.com/1111/11/11/%E3%80%90%E7%BA%BF%E6%AE%B5%E6%A0%91%E3%80%91%20%20L3-017%20%E6%A3%AE%E6%A3%AE%E5%BF%AB%E9%80%92%20(30%E5%88%86)%20%2027%E5%88%86WA%E4%BB%A3%E7%A0%81/index.html">
<meta property="og:site_name" content="蓝湖畔淅淅沥沥的雨">
<meta property="og:description" content="说明 - 2022-05-05 本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。  L3-017 森森快递 (30分) 森森开了一家快递公司，叫森森快递。因为公司刚刚开张，所以业务路">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="1111-11-11T03:06:11.000Z">
<meta property="article:modified_time" content="2022-05-06T07:30:18.641Z">
<meta property="article:author" content="StarsWhisper">
<meta property="article:tag" content="OldBlog(Before20220505)">
<meta property="article:tag" content="线段树">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/atom.xml" title="蓝湖畔淅淅沥沥的雨" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

  
<link rel="stylesheet" href="/plugin/bganimation/bg.css">

  

  <link href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css" rel="stylesheet" type="text/css">
<meta name="generator" content="Hexo 6.1.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <div class="outer">
        <div class="widget-wrap mobile-header">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

        <section id="main"><article id="post-【线段树】  L3-017 森森快递 (30分)  27分WA代码" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90%E7%BA%BF%E6%AE%B5%E6%A0%91%E3%80%91%20%20L3-017%20%E6%A3%AE%E6%A3%AE%E5%BF%AB%E9%80%92%20(30%E5%88%86)%20%2027%E5%88%86WA%E4%BB%A3%E7%A0%81/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      【线段树】  L3-017 森森快递 (30分)  27分WA代码.md
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E6%80%9D%E6%83%B3or%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">思想or数据结构</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="l3-017-森森快递-30分"><a class="markdownIt-Anchor" href="#l3-017-森森快递-30分"></a> L3-017 森森快递 (30分)</h2>
<p>森森开了一家快递公司，叫森森快递。因为公司刚刚开张，所以业务路线很简单，可以认为是一条直线上的N个城市，这些城市从左到右依次从0到(N−1)编号。由于道路限制，第i号城市（i=0,⋯,N−2）与第(i+1)号城市中间往返的运输货物重量在同一时刻不能超过C<br />
​i<br />
​​ 公斤。</p>
<p>公司开张后很快接到了Q张订单，其中j张订单描述了某些指定的货物要从S<br />
​j<br />
​​ 号城市运输到T<br />
​j<br />
​​ 号城市。这里我们简单地假设所有货物都有无限货源，森森会不定时地挑选其中一部分货物进行运输。安全起见，这些货物不会在中途卸货。</p>
<p>为了让公司整体效益更佳，森森想知道如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制？要注意的是，发货时间有可能是任何时刻，所以我们安排订单的时候，必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输，则这两张订单的运输同时受2-3以及3-4两条道路的限制，因为两张订单的货物可能会同时在这些道路上运输。</p>
<h2 id="输入格式"><a class="markdownIt-Anchor" href="#输入格式"></a> 输入格式：</h2>
<p>输入在第一行给出两个正整数N和Q（2≤N≤10<br />
​5<br />
​​ , 1≤Q≤10<br />
​5<br />
​​ ），表示总共的城市数以及订单数量。</p>
<p>第二行给出(N−1)个数，顺次表示相邻两城市间的道路允许的最大运货重量C<br />
​i<br />
​​ （i=0,⋯,N−2）。题目保证每个C<br />
​i<br />
​​ 是不超过2<br />
​31<br />
​​ 的非负整数。</p>
<p>接下来Q行，每行给出一张订单的起始及终止运输城市编号。题目保证所有编号合法，并且不存在起点和终点重合的情况。</p>
<h2 id="输出格式"><a class="markdownIt-Anchor" href="#输出格式"></a> 输出格式：</h2>
<p>在一行中输出可运输货物的最大重量。</p>
<h2 id="输入样例"><a class="markdownIt-Anchor" href="#输入样例"></a> 输入样例：</h2>
<p>10 6<br />
0 7 8 5 2 3 1 9 10<br />
0 9<br />
1 8<br />
2 7<br />
6 3<br />
4 5<br />
4 2</p>
<h2 id="输出样例"><a class="markdownIt-Anchor" href="#输出样例"></a> 输出样例：</h2>
<p>7</p>
<h2 id="样例提示"><a class="markdownIt-Anchor" href="#样例提示"></a> 样例提示：</h2>
<p>我们选择执行最后两张订单，即把5公斤货从城市4运到城市2，并且把2公斤货从城市4运到城市5，就可以得到最大运输量7公斤。</p>
<p>​<br />
#include <iostream><br />
#include <cstdio><br />
#include <cstring><br />
#include <algorithm></p>
<pre><code>const int maxn=1e5+5;

int n,q;
int vv1,vv2;
int ans;

struct Node
&#123;
    int val,lz;
&#125;tree[maxn&lt;&lt;2];
</code></pre>
<p>​<br />
int getMid(int a,int b){ return (a+b)&gt;&gt;1; }</p>
<p>​<br />
​<br />
void build(int l,int r,int rt)<br />
{<br />
tree[rt].lz=0;<br />
if(l==r)<br />
{<br />
std::cin &gt;&gt; tree[rt].val;<br />
return ;<br />
}<br />
else<br />
{<br />
int mid=getMid(l,r);<br />
build(l,mid,rt&lt;&lt;1);<br />
build(mid+1,r,rt&lt;&lt;1|1);<br />
}<br />
tree[rt].val=std::min(tree[rt&lt;&lt;1].val,tree[rt&lt;&lt;1|1].val);<br />
}</p>
<pre><code>void pushDown(int rt)
&#123;
    if(!tree[rt].lz) return ;
    tree[rt&lt;&lt;1].val-=tree[rt].lz;
    tree[rt&lt;&lt;1|1].val-=tree[rt].lz;
    tree[rt&lt;&lt;1].lz+=tree[rt].lz;
    tree[rt&lt;&lt;1|1].lz+=tree[rt].lz;
    tree[rt].lz=0;
&#125;

void update(int sl,int sr,int l,int r,int rt,int val)
&#123;
    if(l&gt;=sl &amp;&amp; r&lt;=sr)
    &#123;
        tree[rt].val-=val;
        tree[rt].lz+=val;
        return ;
    &#125;
    pushDown(rt);
    int mid=getMid(l,r);
    if(sr&lt;=mid) update(sl,sr,l,mid,rt&lt;&lt;1,val);
    else if(sl&gt;mid) update(sl,sr,mid+1,r,rt&lt;&lt;1|1,val);
    else
    &#123;
        update(sl,sr,l,mid,rt&lt;&lt;1,val);
        update(sl,sr,mid+1,r,rt&lt;&lt;1|1,val);
    &#125;
//子树update完之后，根还还还还还还还还要取子树最小值
    tree[rt].val=std::min(tree[rt&lt;&lt;1].val,tree[rt&lt;&lt;1|1].val);
&#125;

int query(int sl,int sr,int l,int r,int rt)
&#123;
    if(l&gt;=sl &amp;&amp; r&lt;=sr) return tree[rt].val;
    pushDown(rt);
    int mn=2147483647,mid=getMid(l,r);
    if(sr&lt;=mid) mn=std::min(mn,query(sl,sr,l,mid,rt&lt;&lt;1));
    else if(sl&gt;mid) mn=std::min(mn,query(sl,sr,mid+1,r,rt&lt;&lt;1|1));
    else
    &#123;
        mn=std::min(mn,query(sl,sr,l,mid,rt&lt;&lt;1));
        mn=std::min(mn,query(sl,sr,mid+1,r,rt&lt;&lt;1|1));
    &#125;
    return mn;
&#125;

bool cmp(std::pair&lt;int ,int &gt; a,std::pair&lt;int ,int &gt; b)
&#123;
    if(a.second-a.first==b.second-b.first) return a.first&lt;b.first;
    return a.second-a.first&lt;b.second-b.first;
&#125;

int main()
&#123;
    std::cin &gt;&gt; n &gt;&gt; q;
    std::pair&lt;int ,int &gt; pa[q];
    build(1,n-1,1);
    ans=0;
    for(int i=0; i&lt;q; i++)
    &#123;
        std::cin &gt;&gt; pa[i].first &gt;&gt; pa[i].second;
        if(pa[i].first&gt;pa[i].second) std::swap(pa[i].first,pa[i].second);
//线段树的一个点表示相邻的一段路，所以要second-1
//但由于题目的城市编号从0开始，这里默认从1开始，所以变成first+1
        pa[i].first+=1;
    &#125;
    std::sort(pa,pa+q,cmp);
    for(int i=0; i&lt;q; i++)
    &#123;
        int ch=query(pa[i].first,pa[i].second,1,n-1,1);
        ans+=ch;
        update(pa[i].first,pa[i].second,1,n-1,1,ch);
    &#125;
    std::cout &lt;&lt; ans;

    return 0;
&#125;
</code></pre>
<p>​</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90%E7%BA%BF%E6%AE%B5%E6%A0%91%E3%80%91%20%20L3-017%20%E6%A3%AE%E6%A3%AE%E5%BF%AB%E9%80%92%20(30%E5%88%86)%20%2027%E5%88%86WA%E4%BB%A3%E7%A0%81/" data-id="cl2uhoedb004ke4j3gh3hgjpo" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E7%BA%BF%E6%AE%B5%E6%A0%91/" rel="tag">线段树</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/1111/11/11/%E3%80%90%E7%BA%BF%E6%AE%B5%E6%A0%91%E7%BB%83%E4%B9%A0%E3%80%91%20%E6%B4%9B%E8%B0%B7%E7%BA%BF%E6%AE%B5%E6%A0%91%E6%A8%A1%E6%9D%BF1%20CF1288E/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">上一篇</strong>
      <div class="article-nav-title">
        
          【线段树练习】 洛谷线段树模板1 CF1288E.md
        
      </div>
    </a>
  
  
    <a href="/1111/11/11/%E3%80%90%E8%83%8C%E5%8C%85DP%E7%BB%83%E4%B9%A0%E3%80%91%E6%B4%9B%E8%B0%B7%20P5020%E8%B4%A7%E5%B8%81%E7%B3%BB%E7%BB%9F%20P1757%E9%80%9A%E5%A4%A9%E4%B9%8B%E5%88%86%E7%BB%84%E8%83%8C%E5%8C%85%20P1064%5BNOIP2006%20%E6%8F%90%E9%AB%98%E7%BB%84%5D%E9%87%91%E6%98%8E%E7%9A%84%E9%A2%84%E7%AE%97%E6%96%B9%E6%A1%88%20P5322%20%5BBJOI2019%5D%E6%8E%92%E5%85%B5%E5%B8%83%E9%98%B5/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">下一篇</strong>
      <div class="article-nav-title">【背包DP练习】洛谷 P5020货币系统 P1757通天之分组背包 P1064[NOIP2006 提高组]金明的预算方案 P5322 [BJOI2019]排兵布阵.md</div>
    </a>
  
</nav>

  
</article>



</section>
        
          <aside id="sidebar">
  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <h1 class="blog-title">蓝湖畔淅淅沥沥的雨</h1>
    <h2 class="blog-subtitle">All tragedy erased, I see only wonders...</h2>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>



    <div class="social-link">
      
        <a class="hvr-bounce-in" href="https://github.com/Wldcmzy" target="_blank" title="Github">
          Github
        </a>
      
        <a class="hvr-bounce-in" href="https://blog.csdn.net/wldcmzy" target="_blank" title="CSDN">
          CSDN
        </a>
      
        <a class="hvr-bounce-in" href="https://space.bilibili.com/83743701" target="_blank" title="bilibili(无技术和学习内容)">
          bilibili(无技术和学习内容)
        </a>
      
    </div>

    <div class="friend-link">
      <h2>友情链接</h2>
      
        <a class="hvr-bounce-in" href="https://shanamaid.github.io/" target="_blank" title="夏娜主题作者的博客">
          夏娜主题作者的博客
        </a>
      
    </div>
  </div>
</div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy;2021 - 2022 StarsWhisper<br>
      由<a href="http://hexo.io/" target="_blank">Hexo</a>强力驱动 | 
      主题-<a target="_blank" rel="noopener" href="https://github.com/ShanaMaid/hexo-theme-shana">Shana</a>(但是魔改)
      
    </div>
    
  </div>
</footer>
    </div>
    

<script src="//apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"></script>
<script src="//apps.bdimg.com/libs/wow/0.1.6/wow.min.js"></script>
<script>
new WOW().init();
</script>   


  
<link rel="stylesheet" href="/plugin/fancybox/jquery.fancybox.css">

  
<script src="/plugin/fancybox/jquery.fancybox.pack.js"></script>




  
<link rel="stylesheet" href="/plugin/galmenu/GalMenu.css">

  
<script src="/plugin/galmenu/GalMenu.js"></script>

  <div class="GalMenu GalDropDown">
      <div class="circle" id="gal">
        <div class="ring">
          
            <a href="/announcement" title="" class="menuItem">公告</a>
          
            <a href="/tags" title="" class="menuItem">标签</a>
          
            <a href="/categories" title="" class="menuItem">分类</a>
          
            <a href="/archives" title="" class="menuItem">归档</a>
          
            <a href="/knightabout" title="" class="menuItem">关于</a>
          
            <a href="/bridges" title="" class="menuItem">传送门</a>
          
        </div>
        
          <audio id="audio" src="#"></audio>
        
      </div> 
</div>
<div id="overlay" style="opacity: 1; cursor: pointer;"></div>
  <script type="text/javascript">var items = document.querySelectorAll('.menuItem');
    for (var i = 0,
    l = items.length; i < l; i++) {
      items[i].style.left = (50 - 35 * Math.cos( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%";
      items[i].style.top = (50 + 35 * Math.sin( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%"
    }</script>
<script type="text/javascript">
  $(document).ready(function() {
    $('body').GalMenu({
      'menu': 'GalDropDown'
    })
  });
</script>

  <section class="hidden-xs"> 
  <ul class="cb-slideshow"> 
    <li><span>苟利</span></li> 
    <li><span>国家</span></li> 
    <li><span>生死以</span></li> 
    <li><span>岂能</span></li> 
    <li><span>祸福</span></li> 
    <li><span>趋避之</span></li> 
  </ul>
</section>

<script src="/js/script.js"></script>




  </div>
</body>
</html>